from typing import *
from math import inf
from sortedcontainers import SortedSet

# class Solution:

#     def threeSumClosest(self, nums: List[int], target: int) -> int:
#         nums.sort()
#         n, ans = len(nums), inf
#         for i in range(n - 2):
#             l, r = i + 1, n - 1
#             while l < r:
#                 s = nums[l] + nums[r] + nums[i]
#                 if s == target:
#                     return target
#                 if abs(s - target) < abs(ans - target):
#                     ans = s
#                 if s < target:
#                     l += 1
#                 else:
#                     r -= 1
#         return ans


# 


# class Solution:

#     def threeSumClosest(self, nums: List[int], target: int) -> int:
#         nums.sort()
#         ss = SortedSet([nums[0] + nums[1]])
#         ans = inf
#         for i in range(2, len(nums)):
#             num = nums[i]
#             t = target - num
#             k = ss.bisect_left(t)
#             if k < len(ss):
#                 if ss[k] == t:
#                     return target
#                 if abs(ss[k] + num - target) < abs(ans - target):
#                     ans = ss[k] + num
#             if k >= 1:
#                 if ss[k - 1] == t:
#                     return target
#                 if abs(ss[k - 1] + num - target) < abs(ans - target):
#                     ans = ss[k - 1] + num
#             for j in range(i):
#                 ss.add(num + nums[j])
#         return ans

# s = Solution()
# print(s.threeSumClosest(nums=[-1, 2, 1, -4], target=1))

# from random import randrange

# arr = []
# for _ in range(10):
#     arr.append(randrange(1,20))
# arr.sort()
# print(arr)

arr = [5, 6, 9, 12, 15, 16, 17, 19]
ss = SortedSet(arr)
# print(ss.bisect_left(4))
print(ss.bisect_left(11))
print(ss.bisect_left(12))
print(ss.bisect_left(13))
# print(ss.bisect_right(4))
print(ss.bisect_right(11))
print(ss.bisect_right(12))
print(ss.bisect_right(13))
from bisect import *
print(bisect_left(arr,11))
print(bisect_left(arr,12))
print(bisect_left(arr,13))
print(bisect_right(arr,11))
print(bisect_right(arr,12))
print(bisect_right(arr,13))